package com.gali.leetcode.day19;

/**
 * @Auther: gali
 * @Date: 2022-08-05 19:37
 * @Description:
 */
public class Solution {
    /**
     * 最小路径和---动态规划
     * @param grid
     * @return
     */
    public static int minPathSum(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
        int [][]dp=new int[rows][columns];
        dp[0][0]=grid[0][0];
        if (grid == null || rows == 0 || columns == 0) {
            return 0;
        }
        for (int i = 1; i < rows ; i++) {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i < columns; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[rows-1][columns-1];
    }

    /**
     * 爬楼梯---动态规划 f(i)=f(i-1)+f(i-2) 类似斐波拉及数列
     * @param n
     * @return
     */
    public static int climbStairs(int n) {
        int p;
        int q=0;//上上一层
        int r=1;//上一层
        for (int i = 0; i < n; i++) {
            p=q;
            q=r;
            r=q+p;
        }
        return r;
    }
}
